package com.primaryAlgorithm;


/**
 * Description: 深度拷贝带有多指针的链表
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-09-27 11:02:20
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-09-27     张李鑫                     1.0         1.0 Version
 */
public class CopyRandomList {
    static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public static Node copyRandomList(Node head) {
        if (head==null){
            return null;
        }
//        if (head.next == null) {
//            Node node = new Node(head.val);
//            if (head.random!=null){
//                node.random=head.random;
//            }
//            return node;
//        }
        Node node = head;
        while (node != null) {
            Node next = node.next;
            Node copyNode = new Node(node.val);
            node.next = copyNode;
            copyNode.next = next;
            node = next;
        }
        node = head;
        while (node != null) {
            if (node.random != null) {
                node.next.random = node.random.next;
            }
            node = node.next.next;
        }
        Node newNode = head.next;
        Node copyNode = null;
        Node next = null;
        while (head != null) {
            next=head.next.next;
            copyNode=head.next;
            copyNode.next=next==null?null:next.next;
            head.next=next;
            head=next;
        }
        return newNode;
    }

    //[[7,null],[13,0],[11,4],[10,2],[1,0]]
    public static void main(String[] args) {
        Node node = new Node(7);
        Node node1 = new Node(13);
        Node node2 = new Node(11);
        Node node3 = new Node(10);
        Node node4 = new Node(1);
//        Node node5 = new Node(56);
//        Node node6 = new Node(57);
//        Node node7 = new Node(58);

        node.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        node1.random = node;
        node2.random = node4;
        node3.random = node2;
        node4.random = node;


        Node node8 = copyRandomList(node);
        node = node.next;
        while (node8 != null) {
            System.out.print("node8 val=" + node8.val);
            System.out.print("node val=" + node.val);

            System.out.print("   ");
            if (null != node8.random) {
                System.out.print("random=" + node8.random.val);
                System.out.print("random=" + node.random.val);
            } else {
                System.out.print("random= null");
            }
            System.out.println();
            node8 = node8.next;
            node = node.next;
        }

    }


}
